package usaco.c2009.february.silver;

import java.util.Scanner;

/*
 * p3199
 * USACO 2009 February - Silver
 */

public class p3199 {

	static int N, K;
	static int mod = 5000011;
	static int[] n;

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		K = scanner.nextInt();
		n = new int[N+1];
		
		for (int i=N;i>=1;--i) {
			if (i==N) {
				n[i] = 2;
			}
			else if (i+K+1 > N) {
				n[i] = (n[i+1] + 1) % mod;
			}
			else {
				n[i] = (n[i+1] + n[i+K+1]) % mod;
			}
		}
		
		System.out.println(n[1]);

	}

}
